// @algorithm @lc id=1000268 lang=typescript
// @test([[17,2,17],[16,16,5],[14,3,19]])  expect: 10
// @title JEj789
function minCost(costs: number[][]): number {
  const m = costs.length;
  // dp[i][j]表示第i间房子且以j为颜色的粉刷最少花费
  // 滚动数组，状态转移只依赖于前一个状态
  const dp: number[][] = new Array(2).fill(0).map((_) => new Array(3).fill(0));
  // 初始化状态
  dp[0] = [...costs[0]];

  for (let i = 1; i < m; i++) {
    const currIdx = i % 2;
    const preIdx = Number(!currIdx);
    // 相邻颜色不能相同，
    // 比如：0颜色的房子，那么它只能从1或者2颜色转移而来
    dp[currIdx][0] = Math.min(dp[preIdx][1], dp[preIdx][2]) + costs[i][0];
    dp[currIdx][1] = Math.min(dp[preIdx][0], dp[preIdx][2]) + costs[i][1];
    dp[currIdx][2] = Math.min(dp[preIdx][1], dp[preIdx][0]) + costs[i][2];
  }
  const idx = (m - 1) % 2;
  // 结果取不同颜色结尾的粉刷成本的最小值
  return Math.min(...dp[idx]);
}
